/**
 * @Auther: wangliuyang
 * @Date: 2021/4/24 18:19
 * @Description:
 */
public class Solution_32 {
    public int longestValidParentheses(String s) {
        int ans = 0;
        if (s == null || s.length() < 2) {
            return ans;
        }
        char[] chars = s.toCharArray();
        int[] dp = new int[s.length()];     //dp数组表示以第i个字符结尾得最长有效括号，全局得最长括号变便为dp数组最大值
        for (int i = 1; i < dp.length; i++) {
            int pre = i - 1 - dp[i - 1];    //右括号要配对的左括号位置；
            if (chars[i] == ')' && pre >= 0 && chars[pre] == '(') {
                dp[i] = dp[i - 1] + 2 + ((pre - 1) >= 0 ? dp[pre - 1] : 0) ;
            }
            ans = Math.max(dp[i] , ans);
        }
        return ans;
    }
}
